B Trees Review Part 2
	The following review questions were covered in Labs 02 and 03 and are questions taken from the course website. NOT ALL questions from the course website were discussed in lab. Please note that the information presented here does not necessarily represent a complete answer to the review question. The information is intended to spark student's memory for those who attended lab OR provide a base (hint) from where to start for those students who did not attend lab.
	Question 1: A B+ Tree of order 200 is to be used to implement an indexed sequential file. There are 5,000 nodes in the sequence set. The average number of keys per node is 100. (This applies to both the sequence set and the index set). For each key in the sequence set there is a pointer to a block of records. The key in the sequence set identifies the last record in the block. The average number of records in the block is 10 although each data block is capable of holding 15 records. A) Sketch the file structure, indicating the number of nodes at each level of the index. B) How many data records are in the file. C) If sequential processing were never needed for the file, it could be structured differently, improving performance both in terms of memory utilization and retrieval time. Suggest and explain how performance can be improved.
	ANSWER A:
	ANSWER B: 5,000,000 records (500,000 blocks x 10 records per block). NOTE: Total Capacity of this structure is 120,000,000 assuming a 2-level index. ANSWER C: Eliminate top level of the sequence set OR use an ordinary B tree. (there are more answers than this!)
	Question 2: Why do we NOT use actual key values as separators in a B+ Tree?
		Sometimes the keys are too large and we waste space (in this case it might be more efficient to use a simple prefix).
	Question 3: What quality of some simple sorts (like bubble sort) make them sometimes preferable to otherwise more efficient sorts when working with large files?
		Locality of records (ie. - less costly swaps from memory to the hard drive).
	Question 4: Why is it a good idea to use the same block size for the index set and the sequence set in a B+ Tree structured file?
		Simplicity and Accessibility.
	Question 5: If we compare a B-Tree with the index set of a B+ Tree what can we say about the function (purpose) of the key values?
		The purpose is essentially the same. In a B- Tree the key represents an actual record that exists, in a B+ Tree this is not necessarily the case.

BACK

© Copyright 2002

Questions? Please Email: gwen@cpsc.ucalgary.ca

Last modified December 5, 2002